package algorithm
{
	import flash.utils.Dictionary;

	//迪杰斯特拉 无向算法
	public class DijkstraNoDirctionAlgorithm
	{

		public function DijkstraNoDirctionAlgorithm()
		{
			
		}
		
		public var startPoint:MapPoint;
		
		public var endPoint:MapPoint;
		
		public  var UndefindPointMap:HashMap;
		
		public  var ShortPointMap:HashMap;
		
		public  var pointMatrix:Dictionary;
		
		public var pointMap:HashMap;
		
		public var shortPathMap:HashMap;
		
		private var _backFun:Function;
		
		private static var _instance:DijkstraNoDirctionAlgorithm;
		
		
		public static function getInstance():DijkstraNoDirctionAlgorithm
		{
			if(!_instance)
			{
				_instance = new DijkstraNoDirctionAlgorithm();			
			}
			
			return _instance;
		
		}
		
		/**
		 * @param pathMap  			记录了路径信息的map
		 * @param startMapPoint		起始点
		 */		
		public  function createTopoMap(pointMap:HashMap,pointMatrix:Dictionary,startMapPoint:MapPoint,endMapPoint:MapPoint,backHandler:Function = null):void
		{
			//初始化
			UndefindPointMap = new HashMap();
			ShortPointMap = new HashMap();
			shortPathMap = new HashMap();
			this.pointMatrix = pointMatrix;
			this.pointMap = pointMap;
			startPoint = startMapPoint;
			endPoint = endMapPoint;
			
			_backFun = backHandler;
			
			//初始化最短路径点map
//			ShortPointMap.put(startMapPoint.mapId,startMapPoint);
			shortPathMap.put(startMapPoint.mapId,0);
			//初始化未知情况点map
			for each(var onePoint:MapPoint in pointMap.dict)
			{
				UndefindPointMap.put(onePoint.mapId,onePoint);
			}
			
			//开始生成路线图
			startFindPath(startPoint);
		}
		
		
		private function startFindPath(middPoint:MapPoint):void
		{
			
			var endPaths:Dictionary = pointMatrix[middPoint.mapId] as Dictionary;//从middPoint到下面若干接点的路径集合
			if(endPaths == null || middPoint == null)
			{
				trace("寻路完毕路了");
				createPath();
				return;
			}
			
			
			var preWeigth:Number;//起点到midd点的权重
			var fromMiddToNextWeight:Number;//midd点到next点的权重
			var sumWeigth:Number;
			var nextPointId:int = -1;
			
			for (var endPointMapId:String in endPaths)
			{
				var oldPathWeigth:Number = shortPathMap.get(int(endPointMapId)) as Number;
				var endPoint:MapPoint = pointMap.get(int(endPointMapId)) as MapPoint;
				if(!oldPathWeigth)//还没有到这个节点的路径
				{
					preWeigth = shortPathMap.get(middPoint.mapId) as Number;//起点到midd点的权重
					fromMiddToNextWeight = pointMatrix[middPoint.mapId][int(endPointMapId)];//midd点到next点的权重
					shortPathMap.put(int(endPointMapId),(preWeigth + fromMiddToNextWeight));
					endPoint.prePoint = middPoint;
					
					if(isNaN(sumWeigth) || (preWeigth + fromMiddToNextWeight) < sumWeigth)//路径较短则选择这个终点
					{
						sumWeigth = preWeigth + fromMiddToNextWeight;
						nextPointId = int(endPointMapId);
					}

				}
				else//存在老的路径到next点
				{
					preWeigth = shortPathMap.get(middPoint.mapId) as Number;//起点到midd点的权重
					fromMiddToNextWeight = pointMatrix[middPoint.mapId][int(endPointMapId)];//midd点到next点的权重
					var tempWeigth:Number = preWeigth+fromMiddToNextWeight;
					
					if(tempWeigth < oldPathWeigth)
					{
						endPoint.prePoint = middPoint;
					}
					
					shortPathMap.put(int(endPointMapId),Math.min(oldPathWeigth,tempWeigth));
					
					
					if(isNaN(sumWeigth) || (preWeigth + fromMiddToNextWeight) < sumWeigth)//路径较短则选择这个终点
					{
						sumWeigth = preWeigth + fromMiddToNextWeight;
						nextPointId = int(endPointMapId);
					}
				}
			}
			
			startFindPath(pointMap.get(nextPointId) as MapPoint);
		}
		private var pathString:String = "";
		private function createPath():void
		{
			
			stepFind(endPoint,[]);
			
			function stepFind(p:MapPoint,paths:Array):void
			{
				if(p == null)
				{
					trace(pathString);
					_backFun(paths.reverse());
					return;
				}
				pathString += p.mapId+"<-";
				paths.push( p.mapId);
				stepFind(p.prePoint,paths);
			}
			
		}
		

	}
}